package me.timlong;

public class LongestCommonSubSequence {

    /**
     * 链接：https://www.nowcoder.com/questionTerminal/c996bbb77dd447d681ec6907ccfb488a
     * 来源：牛客网
     *
     * 对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，
     * 这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,
     * 其中Ui&ltUi+1，Vi&ltVi+1。且A[Ui] == B[Vi]。给定两个字符串A和B，
     * 同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。
     *
     *
     *
     * 解决方案：动态规划的思想
     * f(i, j) -> A串0 - i 与 B串 0 - j的最大公共子序列为
     * 递推式：
     *
     *
     */
    public int findLCS(String A, int n, String B, int m) {
        int[][] res = new int[n + 1][m +1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(A.charAt(i) == B.charAt(j))
                    res[i + 1][j + 1] = res[i][j] + 1;
                else if(A.charAt(i) != B.charAt(j))
                    res[i + 1][j + 1] = Math.max(res[i][j + 1], res[i + 1][j]);
            }
        }
        return res[n][m];
    }

    private int maxTriple(int a, int b, int c){
        return (a > b) ? (a > c ? a : c) : (b > c ? b : c);
    }


    public static void main(String[] args) {
        System.out.println(new LongestCommonSubSequence().findLCS("1A2C3D4B56",10,"B1D23CA45B6A",12));
    }


}
